package com.mj.tree;

import com.mj.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree<E> implements BinaryTreeInfo {
    protected int size;
    protected Node<E> root;//根节点

    protected static class Node<E> {
        Node<E> parent;//常用到
        Node<E> left;
        Node<E> right;
        E element;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        public Node<E> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }
            return null;
        }
    }

    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空所有元素
    public void clear() {
        size = 0;
        root = null;
    }

     //接口只允许定义方法

    public static abstract class Visitor<E> {
        boolean stop;
        /**
         * @param element
         * @return 如果返回true，就代表停止遍历
         */
        abstract boolean visit(E element);
    }


    /**
     * 前序遍历
     */
    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root, visitor);
    }

    private void preorder(Node<E> node, Visitor<E> visitor) {
        //停止递归和打印
        if (node == null || visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        inorderTraversal(root, visitor);
    }

    private void inorderTraversal(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;

        inorderTraversal(node.left, visitor);
        //停止打印
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorderTraversal(node.right, visitor);

//        倒着中序遍历
//        inorderTraversal(node.right);
//        System.out.println(node.element);
//        inorderTraversal(node.left);

    }

    /**
     * 后序遍历
     */
    public void postorderTraversal(Visitor<E> visitor) {
        if (visitor == null) return;
        postorderTraversal(visitor, root);
    }

    private void postorderTraversal(Visitor<E> visitor, Node<E> node) {
        //停止递归
        if (node == null || visitor.stop) return;

        postorderTraversal(visitor, node.left);
        postorderTraversal(visitor, node.right);
        //停止打印
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 层序遍历
     */
    public void levelTraversal(Visitor<E> visitor) {
        if (root == null || visitor == null) return;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            //节点对外不可见
            if (visitor.visit(node.element)) return;
//            System.out.println(node.element);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    /**
     * 给子类提供接口，可返回子类的节点
     *
     * @param element
     * @param parent
     * @return
     */
    protected Node<E> createNode(E element, Node<E> parent) {
        //默认情况下 返回 公共的节点类
        return new Node<>(element, parent);
    }

    /**
     * 前驱节点
     *
     * @return
     */
    protected Node<E> predecessor(Node<E> node) {
        if (node == null) return null;

        //前驱节点在左子树当中（left.right.right.right. . . .)
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        // node.parent = null
        // node == node.parent.right
        return node.parent;
    }

    /**
     * 后驱节点
     *
     * @return
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) return null;

        //前驱节点在右子树当中（right.left.left.left. . . .)
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        // node.parent = null
        // node == node.parent.left
        return node.parent;
    }

    /**
     * 迭代 用层序遍历计算高度
     * 每一层的元素数量是当前队列的长度
     * 元素弹出，队列长度-1
     * 当每一层的所有元素弹出(队列长度等于0)时，这一层就访问完了，height++
     *
     * @return
     */
    public int height() {
        if (root == null) return 0;
        int height = 0;
        //存储着每一层的元素数量
        int levelSize = 1;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
            if (levelSize == 0) {//意味着即将访问下一层
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    /**
     * 递归
     * 每个节点的高度等于 子节点中最大的高度+1
     */
    public int height2() {
        return height2(root);
    }

    private int height2(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height2(node.left), height2(node.right));
    }

    /**
     * 判断一棵树是否为完全二叉树
     *
     * @return
     */
    public boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;
            if (node.hasTwoChildren()) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else if (node.left == null && node.right != null) {
                return false;
            } else {//后面遍历的节点都必须是叶子节点
                leaf = true;
            }
        }
        return true;
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    //打印什么
    @Override
    public Object string(Object node) {
//        Node<E> myNode = (Node<E>) node;
//        String parentString = "null";
//        if (myNode.parent != null) {
//            parentString = myNode.parent.element.toString();
//        }
//        return myNode.element + "_p(" + parentString + ")";
        return node;
    }
}
